// 编写一个程序，通过填充空格来解决数独问题。

// 一个数独的解法需遵循如下规则：

// 数字 1-9 在每一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
// 空白格用 '.' 表示。



/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */

// 暴露接口
const solveSudoku = function (board: string[][]): string[][] {
    // 声明行、列、单元格数组
    const rowsReset: Set<number>[] = new Array(9);
    const colsReset: Set<number>[] = new Array(9);
    const unitsRest: Set<number>[] = new Array(9);
    // 初始化行、列、3x3宫的哈希集合
    for (let i = 0; i < 9; i++) {
        const {
            r,
            c,
            u
        } = solveSudoku_initialHashSet(); // 解构出三组哈希集合
        rowsReset[i] = r;
        colsReset[i] = c;
        unitsRest[i] = u;
    }
    // 先根据初始数独表更新哈希表信息
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] !== '.') {
                rowsReset[i].delete(parseInt(board[i][j]));
                colsReset[j].delete(parseInt(board[i][j]));
                unitsRest[solveSudoku_calUnitIndex(i, j)].delete(parseInt(board[i][j]));
            }
        }
    }
    // 开始初始化填表
    solveSudoku_fillBoard(0, 0, board, rowsReset, colsReset, unitsRest);
    return board;
};
// 初始化哈希集合函数
function solveSudoku_initialHashSet() {
    const numScope: number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    const r: Set<number> = new Set(numScope);
    const c: Set<number> = new Set(numScope);
    const u: Set<number> = new Set(numScope);
    return {
        r,
        c,
        u
    };
}
// 计算当前位置所处的单元格索引
function solveSudoku_calUnitIndex(currR: number, currC: number) {
    return (currR / 3 | 0) * 3 + (currC / 3 | 0);
};
// 填表格函数返回布尔值，采用递归实现
function solveSudoku_fillBoard(currR: number, currC: number,
    board: string[][], rowsReset: Set<number>[],
    colsReset: Set<number>[], unitsRest: Set<number>[]): boolean {
    // 换行
    if (currC === 9) {
        currR++;
        currC = 0;
        // 都填完了直接返回，递归出口5
        if (currR === 9) {
            return true;
        }
    }
    // 如果是原始填过的数字则直接填下一格
    if (board[currR][currC] !== '.') {
        return solveSudoku_fillBoard(currR, currC + 1, board, rowsReset, colsReset, unitsRest);
    }
    let unitIndex: number = solveSudoku_calUnitIndex(currR, currC);
    for (let i = 1; i <= 9; i++) {
        // 如果当前数不可用直接跳到下一个
        if (!rowsReset[currR].has(i) || !colsReset[currC].has(i) || !unitsRest[unitIndex].has(i)) {
            continue;
        }
        // 如果当前数可用，则更新哈希表信息，往表格里填数字
        let currStr: string = String(i);
        board[currR][currC] = currStr; // 填表
        rowsReset[currR].delete(i);
        colsReset[currC].delete(i);
        unitsRest[unitIndex].delete(i);
        // 继续往下填表，如果不满足则需要回溯
        if (solveSudoku_fillBoard(currR, currC + 1, board, rowsReset, colsReset, unitsRest) === false) {
            rowsReset[currR].add(i);
            colsReset[currC].add(i);
            unitsRest[unitIndex].add(i);
            board[currR][currC] = '.';
        } else {// 满足则返回真值
            return true;
        }
    }
    // 所有的1 - 9数字都填不了下一个则返回false
    return false;
}


solveSudoku([
    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"]
])